package junior.DynamicProgramming动态规划;



public class 矩阵最大路径和 {
    static int totlepath =0;
    static int n = 8;  //n行数阵
    public static void main(String[] args) {

//        int[][] a= {{22,0,0,0,0,0},//原始数阵,边界控制
//                    {30,16,0,0,0,0},
//                    {10,22,18,0,0,0},
//                    {27,13,1,22,0,0},
//                    {9,28,10,14,15,0},
//                    {0,0,0,0,0},};
        int[][] a= {{22,0,0,0,0,0,0,0,0},//原始数阵,边界控制
                    {30,16,0,0,0,0,0,0,0},
                    {10,22,18,0,0,0,0,0,0},
                    {27,13,1,22,0,0,0,0,0},
                    {9,28,10,14,15,0,0,0,0},
                    {23,19,26,12,21,26,0,0},
                    {8,17,1,18,25,28,27,0,0},
                    {11,23,18,8,15,25,13,15,0},
                    {0,0,0,0,0,0,0,0,0}
        };
        int[][] b= new int[n+1][n+1]; //状态转移数阵
//        状态转移数阵，最下面一行初始化
        for (int i = 0; i < n; i++) {
            b[n][i] = a[n][i];
        }
//        状态转移
        for (int i = n-1; i >=0; i--) {
            for (int j = 0; j <=i; j++) {
                if (b[i+1][j] >= b[i+1][j+1]) //包含两种状态吗，左边大于右边，左边等于右边
                    b[i][j] = a[i][j] + b[i+1][j];
                else
                    b[i][j] = a[i][j] + b[i+1][j+1];
            }
        }
//        输出结果
        System.out.println("最大路径和为："+b[0][0]);
//        输出所有状态转移
        System.out.println("输出所有状态转移:");
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                System.out.print(b[i][j]+" ");
            }
            System.out.println();
        }

//        输出最大路径(附带最大路径条数)
        System.out.println("输出所有最大路径:");
        int[] path = new int[100];
        showpath(b,path,0,0,0);
//        输出最大路径条数
        System.out.println("最大路径条数:"+ totlepath);



    }

    public static void showpath(int[][] b,int[] path,int i,int j,int k){
        if(k==n-2){  //从n-2判断结束，边界控制技巧,
            totlepath++;
            int max = Math.max(b[i+1][j] , b[i+1][j+1]);
            path[k]=b[i][j]-max;
            path[k+1]=max;
            for (int l = 0; l <= k; l++) {
                System.out.print(path[l]+" ");
            }
            System.out.println();
            return;
        }
        if(b[i+1][j] > b[i+1][j+1]){
            path[k] = b[i][j]-b[i+1][j];
            showpath(b,path,i+1,j,k+1);
        }
        if(b[i+1][j] < b[i+1][j+1]){
            path[k] = b[i][j]-b[i+1][j+1];
            showpath(b,path,i+1,j+1,k+1);
        }
        if(b[i+1][j] == b[i+1][j+1]){
            path[k] = b[i][j]-b[i+1][j];
            showpath(b,path,i+1,j,k+1);
            path[k] = b[i][j]-b[i+1][j+1];
            showpath(b,path,i+1,j+1,k+1);
        }
        // 核心：k+1传递给下一个递归节点入口函数，但是回到现场时，k是当前现场的参数值，不是递归改变的，相当于退栈
//      且k是path数组的下标，存储遍历到当前节点的值，结束上一个递归节点，k还是参数的值，从下一个方向的递归节点开始，重新赋值，达到更新效果
    }
}
